public class BinarySearchTree
{

	private BinaryNode root;

    
    /* constructor */

    public BinarySearchTree( )
    {
    	root = null;
	}


    /* isEmpty */

    public boolean isEmpty( )
    {
		return (root == null);
    }


    /* makeEmpty */

    public void makeEmpty( )
    {
		root = null;
    }


    /* insert */

    public void insert( Comparable x )
    {
		root = insert(x, root);
    }

	private BinaryNode insert( Comparable x, BinaryNode t ) {
		
		if (t == null) {
			return new BinaryNode( x );
		}
		else {
			int cmp = x.compareTo( t.element );
			if (cmp < 0) {
				t.left = insert( x, t.left );
			}
			else if (cmp > 0) {
				t.right = insert( x, t.right );
			}
			else {
				throw new DuplicateItemException( x.toString() );
			}
		}

		return t;
	}


    /* find */

    public Comparable find( Comparable x )
    {
		return elementAt( find( x, root ) );
    }

	private Comparable elementAt( BinaryNode t ) {
		
		return ((t != null) ? t.element : null);
	}

	private BinaryNode find( Comparable x, BinaryNode t ) {
	
		if (t == null) {
			return null;
		}
		else {
			int cmp = x.compareTo( t.element );
			if (cmp < 0) {
				return find( x, t.left );
			}
			else if (cmp > 0) {
				return find( x, t.right );
			}
			else {
				return t;
			}
		}
	}


    /* findMax */

    public Comparable findMax( )
    {
		return elementAt( findMax( root ) );
    }

	private BinaryNode findMax( BinaryNode t ) {

		if (t == null) {
			return null;
		}
		else if ( t.right != null ) {
			return findMax( t.right );
		}
		else {
			return t;
		}
	}


    /* findMin */

    public Comparable findMin( )
    {
		return elementAt( findMin( root ) );
    }

	private BinaryNode findMin( BinaryNode t ) {

		if (t == null) {
			return null;
		}
		else if ( t.left != null ) {
			return findMin( t.left );
		}
		else {
			return t;
		}
	}


    /* removeMin */

    public void removeMin( )
    {
		if (root == null) {
			throw new ItemNotFoundException();
		}
		
		root = removeMin( root );
    }

	private BinaryNode removeMin( BinaryNode t ) {
		
		if ( t.left != null ) {
			t.left = removeMin( t.left );
			return t;
		}
		else {
			return t.right;
		}
	}


    /* remove */

    public void remove( Comparable x )
    {
		root = remove( x, root );
    }

	private BinaryNode remove( Comparable x, BinaryNode t ) {
		
		if (t == null) {
			throw new ItemNotFoundException( x.toString() );
		}
		else {
			int cmp = x.compareTo( t.element );
			if (cmp < 0) {
				t.left = remove( x, t.left );
				return t;
			}
			else if (cmp > 0) {
				t.right = remove( x, t.right );
				return t;
			}
			else {
				// found it!
				if (t.left != null && t.right != null) {
					// 2 children
					t.element = findMin( t.right ).element;
					t.right = removeMin( t.right );
					return t;
				}
				else if (t.left != null || t.right != null) {
					// 1 child
					return ((t.left != null) ? t.left : t.right);
				}
				else {
					// 0 children
					return null;
				}
			}
		}
	}

}